package algorithm.minitree;
import java.util.Vector;

/**
 * @author bingo
 * @Description   最小生成树(带权无向图，连通图)-------->prim 算法   运用切分定理,暂未优化
 * @Date 2018/4/17
 */
public class LazyPrimMST<Weight extends Number & Comparable >{
    /**图的引用*/
    private  WeightedGraph<Weight> G;
    /**标记数组**/
    private  boolean[] marked;
    /**最小堆*/
    private MinHeap<Edge<Weight>> minHeap;
   /**生成最小树所有的边*/
    private Vector<Edge<Weight>> mst;
   /**最小生成树的权值*/
    private Number mstWeight;

    public LazyPrimMST(WeightedGraph weightedGraph) {
        this.G = weightedGraph;
        marked = new boolean[G.V()];
        minHeap = new MinHeap(G.E());
        mst = new Vector(G.V());
        visit(0);
        while(!minHeap.isEmpty()){
            Edge<Weight>  e =   minHeap.pop();
            /**如果这两条边都被标记过，则扔掉这条边**/
            if(marked[e.a()]==marked[e.b()]){
                continue;
            }
            mst.add(e);
            if(!marked[e.a()]){
                visit(e.a());
            }
            else{
                visit(e.b());
            }

        }

        mstWeight = mst.get(0).wt();
        for(int i=1;i<mst.size();i++){
            mstWeight  =  mstWeight.doubleValue() + mst.get(i).wt().doubleValue();
        }

    }
    private void visit(int i) {
        assert !marked[i];
        marked[i] = true;
       for(Edge<Weight> e: G.adj(i)){
           if(!marked[e.getOther(i)]){
               minHeap.insert(e);
           }

       }
    }

    public Vector<Edge<Weight>> getMst(){

        return  mst;
    }

    /***返回最小生成树的权值*/
    public Number getMstWeight(){

        return  mstWeight;
    }
}
